A portion of the disclosure of this patent document contains material which is subject to copyright protection. The copyright owner has no objection to the xeroxographic reproduction by anyone of the patent document or the patent disclosure in exactly the form it appears in the Patent and Trademark Office patent file or records, but otherwise reserves all copyright rights whatsoever.
The invention relates generally to computing systems, and more particularly to a method of compressing characters, including alphanumeric and other character types.
Data compression in computing systems has been used for some time to compress data or characters (e.g., letters, numbers, punctuation marks, or other symbols, including at times control codes) for transmission from one computing system element to another, or for storage (e.g., memory or secondary storage such as disk systems). Data compression operates to achieve faster transmission of the data, and conservation of storage space. Some compression techniques are capable of achieving high compression rates, but at the expense of large program size, performance time, or both. Data compression, therefore, can be a tradeoff between performance, program size, and compression rate.
The present invention provides a compromise, achieving a good compression rate using a technique that allows the use of a relatively small, efficient program to compress groups of characters.
Broadly, the invention is directed to representing characters by a first code, indicating the number of characters being compressed, and for each character a second code that identifies the character. In one embodiment of the invention, the first code is three bits, and the second code is six bits.
In a preferred embodiment, the invention is used to compress groups of characters, each eight bits in size. A first code identifies the number of characters in the group, and for each character in the group, a second code identifies the particular character. In certain instances, characters that cannot be represented by the second code are represented by a third code, eight bits in size, with the second code pertaining to that character identifying the third code.
The invention finds particular use in the environment of interconnect testing of a computing system employing boundary scan cells. Each cell is specifically identified according to the integrated circuit chip on which it is formed, the particular pin with which it is associated, the generic identification of the integrated circuit, and pin number. Much of this information is redundant and can be easily compressed. However, the pin number, if left in its original designation, will tend to take up a large amount of room. Accordingly, the present invention is used to form a pair of string arrays containing the pin identifications for each boundary cell.
A number of advantages are achieved by the present invention. First, a small, simple program is capable of achieving high compression rates so that boundary cell names, used in testing, can be compressed to a high degree.
A further advantage of the invention is that the storage necessary, for both the compression and decompression program, as well as the compressed data, is significantly reduced.